package com.onepiece.shipelves.common.myutils.sort;

public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {3,7,1, 2, 3, 5, 2, 6, 9, 3, 2, 1};
        int[] sortArray = sortArray(nums);
        for (int i = 0; i < sortArray.length; i++) {
            System.out.println(sortArray[i]);
        }

    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

    private static int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        mergeSort(nums, 0, nums.length - 1);//right表示最后一个数字
        return nums;
    }

    private static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int q = (left + right) / 2;
        //这里和快排不一样的是要包含q
        mergeSort(nums, left, q);
        mergeSort(nums, q + 1, right);
        merge(nums, left, q, right);

    }

    //这里申请一个额外空间用于做合并数组，需要注意现在传入的right是数组最后的位置
    private static void merge(int[] nums, int left, int q, int right) {
        int i = left, j = q + 1, k = 0;
        int[] temp = new int[right - left + 1];//因为right为位置所以需要+1才是数组的长度
        while (i <= q && j <= right){
            if(nums[i] < nums[j]){
                temp[k++] = nums[i++];
            }else {
                temp[k++] = nums[j++];
            }
        }
        int start = i,end = q;
        if(j <= right){
            start = j;
            end = right;
        }
        while (start <= end){
            temp[k++] = nums[start++];
        }
        for (int l = 0; l <= right - left; l++) {//这里要加等于也是因为right为位置
            nums[left + l] = temp[l];
        }


    }


}
